package 剑指offer.堆栈队列;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * 输入 n 个数，找出其中最小的 K 个数
 *
 * TOPK问题：找最小的K个数
 * 所涉及的数据结构就是 大顶堆
 */
public class 第40题最小的K个数 {

    /*
    结果要得到原始数据流的最小K个数据
    可以构建一个大顶堆

    先拿前 k 个数据构建一个大顶堆
    然后从 k+1 开始，若遍历的节点大于等于堆顶元素则丢弃，若小于的话则加入

    注意要维持大顶堆的长度不能超过 K
     */
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (input == null || k == 0 || k > input.length)
            return ans;
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, ((o1, o2) -> o2 - o1));
        // 先把前K个数据加入到大根堆里面
        for (int i = 0; i < k; i++) {
            queue.add(input[i]);
        }
        // 然后从第K个元素开始继续修改大根堆，注意不要让大根堆长度大于K了
        for (int i = k; i < input.length; i++) {
            if (input[i] < queue.peek()) {
                queue.add(input[i]);
                queue.poll();
            }
        }
        // 最后输出大根堆里面的结果
        while (queue.size() != 0) {
            ans.add(queue.poll());
        }
        Collections.reverse(ans);
        return ans;
    }

    public static void main(String[] args) {
        int[] input = {4, 5, 1, 6, 2, 7, 3, 8};
        int k = 10;
        ArrayList<Integer> ans = GetLeastNumbers_Solution(input, k);
        System.out.println();
    }
}
